#pragma GCC optimize(2)
#include <iostream>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <unordered_set>
#include <bitset>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N=2e5+10;
int a[N];
int cnt,k,n;

int main()
{
	int t;
	cin>>t;
	
	while(t--)
	{
		cin>>n>>k;
		int cnt=0;
		for(int i=1;i<=n;i++)
		{
			int f2=i;
			int f1=n;
			for(int j=1;j<=k-2;j++)
			{
				int t=f1-f2;
				f1=f2;
				f2=t;
				if(f2>f1)
				{
					break;
				 }	
			}
			if(f1>=f2) cnt++;
			
		}
		cout<<cnt<<endl;
	}

	return 0;
}

